package algorithmExample.sort;

import javafx.collections.transformation.SortedList;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: zhangrongqing
 * @Date: 2019/11/19 10:07
 */
//题目:https://leetcode-cn.com/problems/merge-intervals/
public class MergeInterval {
    public int highValue = 0;

    public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) {
            return new int[][]{};
        }
        if (intervals.length == 1) {
            return intervals;
        }
        int[][] sortedArray = sorted(intervals);
        List<int[]> tmpList = new ArrayList<>();
        int pos = 0;
        while (pos < sortedArray.length) {
            int currentPos = calcPos(sortedArray, pos);
            int[] tmp = new int[]{sortedArray[pos][0], Math.max(highValue, sortedArray[currentPos][1])};
            tmpList.add(tmp);
            pos = currentPos + 1;
        }
        int[][] result = new int[tmpList.size()][];
        int length = 0;
        for (int[] tmp : tmpList) {
            result[length] = tmp;
            length++;
        }
        return result;
    }

    private int calcPos(int[][] sortedArray, int pos) {
        int result = pos;
        if (pos >= sortedArray.length - 1) {
            return result;
        }
        if (sortedArray[pos][1] >= sortedArray[pos + 1][0] || highValue >= sortedArray[pos + 1][0]) {
            highValue = Math.max(highValue, Math.max(sortedArray[pos][1], sortedArray[pos + 1][1]));
            return calcPos(sortedArray, pos + 1);
        } else {
            highValue = Math.max(highValue, sortedArray[pos][1]);
            return result;
        }
    }


    private int[][] sorted(int[][] intervals) {
        for (int i = 0; i < intervals.length; i++) {
            for (int j = 0; j < intervals.length - i - 1; j++) {
                if (intervals[j][0] > intervals[j + 1][0]) {
                    int[] tmp;
                    tmp = intervals[j];
                    intervals[j] = intervals[j + 1];
                    intervals[j + 1] = tmp;
                }
            }
        }
        return intervals;
    }
}
